package com.mlh.dp.回文;

/**
 * @author 缪林辉
 * @date 2024/5/27 12:45
 * @DESCRIPTION
 */
// 给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
// 回文字符串 是正着读和倒过来读一样的字符串。
// 子字符串 是字符串中的由连续字符组成的一个序列。
// 输入：s = "aaa"
// 输出：6
// 解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
public class 回文子串 {
    //思路流程：本题如果我们定义，dp[i] 为 下标i结尾的字符串有 dp[i]个回文串的话，我们会发现很难找到递归关系。
    //我们在判断字符串S是否是回文，那么如果我们知道 s[1]，s[2]，s[3] 这个子串是回文的，
    // 那么只需要比较 s[0]和s[4]这两个元素是否相同，如果相同的话，这个字符串s 就是回文串。
    //所以为了明确这种递归关系，我们的dp数组是要定义成一位二维dp数组。
    // 布尔类型的dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。
    public int method1(String s) {
        int len=s.length();
        boolean[][]dp=new boolean[len][len];//行为字符串头，列为字符串尾
        int result=0;//记录回文子串的数量
        //根据递推公式，确定遍历顺序
        //从递推公式中可以看出，情况三是根据dp[i + 1][j - 1]是否为true，在对dp[i][j]进行赋值true的。
        //dp[i + 1][j - 1] 在 dp[i][j]的左下角
        //因此从下到上遍历
        for (int i = len-1; i >=0; i--) {
            for (int j = i; j < len; j++) {
                //在确定递推公式时，就要分析如下几种情况。
                // 整体上是两种，就是s[i]与s[j]相等，s[i]与s[j]不相等这两种。
                // 当s[i]与s[j]不相等，那没啥好说的了，dp[i][j]一定是false。
                // 当s[i]与s[j]相等时，这就复杂一些了，有如下三种情况
                // 情况一：下标i 与 j相同（j-i=0），同一个字符例如a，当然是回文子串
                // 情况二：下标i 与 j相差为1（j-i=1），例如aa，也是回文子串
                // 情况三：下标：i 与 j相差大于1的时候(j-i>1)，例如cabac，此时s[i]与s[j]已经相同了，
                // 我们看i到j区间是不是回文子串就看aba是不是回文就可以了，
                // 那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i + 1][j - 1]是否为true。
                if(s.charAt(i)==s.charAt(j)){
                    if(j-i<2){
                        dp[i][j]=true;
                        result++;
                    }else{
                        if(dp[i+1][j-1]){
                            dp[i][j]=true;
                            result++;
                        }
                    }
                }
            }
        }
        return result;
    }
}
